<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

<script>
    // 8. 定义一个整型数组，保存10个数据，利用程序完成将最大值保存在数组中第1个元素的操作，
    // 使用冒泡、选择、插入排序对数组进行排序（升序降序都可以）。
    let array = Array(10000);
    for (let i = 0; i < array.length; i++) {
        let r = Math.floor(Math.random() * 10000 + 1);
        array[i] = r;
    }
    // 取最大值
    // array[0] = Math.max(...array);
    console.log(array);

    function bubble(array) {
        // 执行时间
        let t1 = new Date().getTime();//开始时间点
        let count = 0; // 执行次数
        let jiaohuan = 0; // 交换次数
        // array = [93, 28, 26, 39, 90, 62, 93, 2, 76, 37];
        // 冒泡排序：两两相邻比较，冒泡一般是从小到大
        for (let i  = 1; i < array.length; i++) { // 控制次数
            for (let j = 0; j < array.length - i; j++) {
                // 两两相邻比较，然后交换
                if (array[j] > array[j + 1]) {
                    array[j]  = array[j] ^ array[j + 1];
                    array[j + 1]  = array[j] ^ array[j + 1];
                    array[j]  = array[j] ^ array[j + 1];
                    jiaohuan++;
                }
                count++;
            }
        }
        console.log(`冒泡排序，执行次数: ${count}，交换次数: ${jiaohuan}`);
        console.log(array);
        let t2 = new Date().getTime();//结束时间点
        console.log("执行时间：", (t2 - t1))
    }
    bubble(array);

    // 选择排序：每次选出最小未排序的元素中最小元素的索引进行排序
    function selectSort(array) {
        // 执行时间
        let t1 = new Date().getTime();//开始时间点
        let count = 0; // 执行次数
        let jiaohuan = 0; // 交换次数
        // array = [93, 28, 26, 39, 90, 62, 93, 2, 76, 37];
        for (let i  = 0; i < array.length - 1; i++) { // 控制次数
            let minIndex = i; //假设i就是最小元素的索引
            for (let j = i + 1; j < array.length; j++) {
                // 选出最小元素的索引
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
                count++;
            }
            // 在此处交换，但是要注意不能是元素本身
            if (minIndex != i) {
                array[i] = array[minIndex] ^ array[i];
                array[minIndex] = array[minIndex] ^ array[i];
                array[i] = array[minIndex] ^ array[i];
                jiaohuan++;
            }
        }
        console.log(`选择排序，执行次数: ${count}，交换次数: ${jiaohuan}`);
        console.log(array);
        let t2 = new Date().getTime();//结束时间点
        console.log("执行时间：", (t2 - t1))
    }
    selectSort(array.filter(() => true));

    // 插入排序：假设第一个元素已经是一个有序数组，从第二个元素开始，将要插入的元素，插入到合适的位置上
    function insertSort(array) {
        // 执行时间
        let t1 = new Date().getTime();//开始时间点
        let count = 0; // 执行次数
        let jiaohuan = 0; // 交换次数
        // array = [93, 28, 26, 39, 90, 62, 93, 2, 76, 37];
        // array = [28, 93, 26, 39, 90, 62, 93, 2, 76, 37];
        for (let i  = 1; i < array.length; i++) { // 控制次数
            let insertIndex = i; // 要插入的元素索引
            let insertItem = array[insertIndex]; //保存要插入的元素值
            for (let j = i - 1; j >= 0; j--) {
                // 预留位置，把大的元素往后移
                if (insertItem < array[j]) {
                    array[j + 1] = array[j];
                    // 如果小于或相等则表示j就是需要插入的位置
                    insertIndex = j;
                    jiaohuan++;
                } else {
                    break;
                }
                count++;
            }
            // 把要插入的元素放到合适的位置上
            if (insertItem != array[insertIndex]) {
                array[insertIndex] = insertItem;
            }
            // console.log(array);
        }
        console.log(`插入排序，执行次数: ${count}，交换次数: ${jiaohuan}`);
        console.log(array);
        let t2 = new Date().getTime();//结束时间点
        console.log("执行时间：", (t2 - t1))
    }
    insertSort(array.filter(() => true));
</script>
</body>
</html>